package com.uraurora.crescent.advanced.tree.impl;

import com.uraurora.crescent.advanced.tree.AbstractSegmentTree;
import com.uraurora.crescent.advanced.tree.ISegmentTree;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.uraurora.crescent.util.SeiIterables;

import java.util.Iterator;
import java.util.List;
import java.util.function.BinaryOperator;

/**
 * @author gaoxiaodong
 */
public class ArraySegmentTree<T> extends AbstractSegmentTree<T> implements ISegmentTree<T> {

    private final static int START_INDEX = 0;

    private T[] data;

    private T[] tree;

    private int size;

    private int dataSize;

    private final BinaryOperator<T> updateMerge;

    // 用来优化区间更新的tag
    private T[] tag;

    public ArraySegmentTree(Iterable<T> iterable,
                            BinaryOperator<T> updateMerge) {

        this.dataSize = Iterables.size(iterable);
        this.size = calculateTreeSize(dataSize);
        this.updateMerge = updateMerge;

        @SuppressWarnings("unchecked")
        T[] data = (T[]) SeiIterables.toArray(iterable, dataSize);
        this.data = data;

        @SuppressWarnings("unchecked")
        T[] tree = (T[]) new Object[calculateTreeSize(dataSize)];
        this.tree = tree;
        buildTree(this.data, this.tree, START_INDEX, START_INDEX, dataSize-1);
    }

    public ArraySegmentTree(T[] objects,
                            BinaryOperator<T> updateMerge){
        dataSize = objects.length;
        this.size = calculateTreeSize(dataSize);
        this.updateMerge = updateMerge;

        @SuppressWarnings("unchecked")
        T[] data = (T[]) new Object[dataSize];
        System.arraycopy(objects, START_INDEX, data, START_INDEX, dataSize);
        this.data = data;

        @SuppressWarnings("unchecked")
        T[] tree = (T[]) new Object[calculateTreeSize(dataSize)];
        this.tree = tree;
        buildTree(this.data, this.tree, START_INDEX, START_INDEX, dataSize-1);
    }

    @Override
    public boolean update(int index, T value) {
        checkIndexRange(index, START_INDEX, dataSize-1);
        internalUpdate(data, tree, START_INDEX, START_INDEX, dataSize-1, index, value);
        return true;
    }

    @Override
    // FIXME: 区间更新，nlogn的时间复杂度
    public boolean update(int left, int right, T value) {
        boolean res = true;
        for (int i = left; i < right + 1; i++) {
            res &= update(i, value);
        }
        return res;
    }

    @Override
    public T query(int index, T initValue) {
        checkIndexRange(index, START_INDEX, dataSize-1);
        return internalQuery(tree, START_INDEX, START_INDEX, dataSize-1, index, index, initValue);
    }

    @Override
    public T query(int left, int right, T initValue) {
        if(left > right){
            throw new IndexOutOfBoundsException("check bounds of the index: left <= right where left:"+left+" right:"+right);
        }
        checkIndexRange(left, START_INDEX, dataSize-1);
        checkIndexRange(right, START_INDEX, dataSize-1);
        return internalQuery(tree, START_INDEX, START_INDEX, dataSize-1, left, right, initValue);
    }

    public boolean set(int index, T value) {
        checkIndexRange(index, START_INDEX, dataSize-1);
        internalSet(data, tree, START_INDEX, START_INDEX, dataSize-1, index, value);
        return true;
    }

    public T get(int index){
        checkIndexRange(index, START_INDEX, dataSize - 1 );
        return this.data[index];
    }

    @Override
    public Iterator<T> iterator() {
        final List<T> res = Lists.newLinkedList();
        dfsHelper(tree, START_INDEX, res);
        return res.iterator();
    }

    private void dfsHelper(T[] arr, int index, List<T> res){
        if(index >= size() || index < 0 || arr[index] == null){
            return;
        }
        int left = 2 * index + 1, right = 2 * index + 2;
        res.add(arr[index]);
        dfsHelper(arr, left, res);
        dfsHelper(arr, right, res);
    }

    @Override
    // FIXME：不要忘了实现size，表示线段树所有的个数，包含空节点
    public int size() {
        return this.size;
    }

    //<editor-fold desc="Private Methods">

    /**
     * 内部建树函数，使用递归方式，将输入的数组使用完全二叉树结构构件线段树
     * 如果树节点索引为node, 则左右子节点索引分别为2 * node + 1， 2 * node + 2
     * @param arr 输入数组
     * @param tree 构建的线段树数组，使用完全二叉树形式
     * @param node 线段树节点索引
     * @param start 建树的开始位置
     * @param end 建树的结束位置
     */
    private void buildTree(T[] arr, T[] tree, int node, int start, int end){
        if (start == end) {
            tree[node] = arr[start];
        }
        else {
            int mid = start + end >> 1;
            int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
            buildTree(arr, tree, leftNode, start, mid);
            buildTree(arr, tree, rightNode, mid + 1, end);
            tree[node] = updateMerge.apply(tree[leftNode], tree[rightNode]);
        }
    }

    /**
     * 内部修改值的递归函数，将线段树中的值进行修改
     * @param arr 输入数组
     * @param tree 构建的线段树数组，使用完全二叉树形式
     * @param node 线段树节点索引
     * @param start 树的开始位置
     * @param end 树的结束位置
     * @param index 需要修改的值的索引
     * @param val 需要修改的值
     */
    private void internalSet(T[] arr, T[] tree, int node, int start, int end, int index, T val){
        if (start == end) {
            arr[index] = val;
            tree[node] = val;
        }
        else {
            int mid = start + end >> 1;
            int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
            if (index >= start && index <= mid) {
                internalSet(arr, tree, leftNode, start, mid, index, val);
            }
            else{
                internalSet(arr, tree, rightNode, mid+1, end, index, val);
            }
            tree[node] = updateMerge.apply(tree[leftNode], tree[rightNode]);
        }
    }

    /**
     * 内部更新值的递归函数，将线段树中的值进行更新
     * @param arr 输入数组
     * @param tree 构建的线段树数组，使用完全二叉树形式
     * @param node 线段树节点索引
     * @param start 树的开始位置
     * @param end 树的结束位置
     * @param index 需要更新的值的索引
     * @param val 需要更新的值
     */
    private void internalUpdate(T[] arr, T[] tree, int node, int start, int end, int index, T val){
        if (start == end) {
            arr[index] = updateMerge.apply(arr[index], val);
            tree[node] = updateMerge.apply(tree[node], val);
        }
        else {
            int mid = start + end >> 1;
            int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
            if (index >= start && index <= mid) {
                internalUpdate(arr, tree, leftNode, start, mid, index, val);
            }
            else{
                internalUpdate(arr, tree, rightNode, mid+1, end, index, val);
            }
            tree[node] = updateMerge.apply(tree[leftNode], tree[rightNode]);
        }
    }

    /**
     * 内部查询指定索引范围的值，采用递归方式
     * @param tree 输入数组
     * @param node 构建的线段树数组，使用完全二叉树形式
     * @param start 线段树节点起始索引
     * @param end 线段树节点结束索引
     * @param left 查询的左边界
     * @param right 查询的右边界
     * @param initValue 查询中的merge初始值
     * @return 范围查询的值
     */
    private T internalQuery(T[] tree, int node, int start, int end, int left, int right, T initValue){
        if (right < start || left > end) {
            return initValue;
        }
        else if(start == end){
            return tree[node];
        }
        else if(left <= start && right >= end){
            return tree[node];
        }
        else {
            int mid = start + end >> 1;
            int leftNode = 2 * node + 1, rightNode = 2 * node + 2;
            T resLeft = internalQuery(tree, leftNode, start, mid, left, right, initValue);
            T resRight = internalQuery(tree, rightNode, mid+1, end, left, right, initValue);
            return updateMerge.apply(resLeft, resRight);
        }
    }


    /**
     * 计算完全二叉树的节点树，并非是真正的节点个数，因为完全二叉树形式的实现，会导致
     * 叶子节点有很多无用的节点
     * @param n 区间范围的元素个数
     * @return 计算开辟的树空间中节点的个数
     */
    private int calculateTreeSize(int n){
        return (int) (Math.pow(2, Math.ceil(log(2, n) + 1)) - 1);
    }

    private int calculateTreeNodeSize(int n){
        return 2 * n + 1;
    }

    public static double log(double base, double value) {
        return Math.log(value) / Math.log(base);
    }

    //</editor-fold>
}
